}slnodetype;

slnodetype *p,*q,*s;

void merge(slnodetype *la,slnodetype *lb) { slnodetype *p;

p=lb->next; Lb->next= la->next;

la->next=p->next; free(p); }

14、statas InsertDubList (DuLinkList &L, int e) {

malloc(f); f->data=Y;

if(p->next==null) {

p->next=f; f->prior=p; } else {

f->prior=p; p->next ->prior=f; f->next=p->next; p->next=f; } }

15、Statas delete(cirLinkList&L) {

If(L=null)

Error(‘nodata’); If(p→next=L) {

L→next=L; L→prior=L. Free(p); } Else {

p→prior→next=→next; p→next→prior=→prior; free(p);

- 25 -

} }

16、statas change (CirLinkList &L) {

If(L=null)

error(‘nodata’); else

If(p->next==null) error(‘can’t change’) else {

q=p->next; p->prior->next=q; q->prior=p->prior; p->next=q->next; q->next=p; p->prior=q; }

19、void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)

{ //已知带头结点的单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 LinkList pa, pb, pc; pa = La->next; pb = Lb->next;

Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa && pb) {

if (pa->data data)

{ pc->next = pa; pc = pa; pa = pa->next; } Else

{ pc->next = pb; pc = pb; pb = pb->next; } }

pc->next = pa ? pa : pb; // 插入剩余段

free(Lb); // 释放Lb的头结点 } // MergeList_L

- 26 -

数据结构复习题：线性表 填空题

1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。

2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。

3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。

4、在线性表的顺序存储中，元素之间的逻辑关系是通过__________决定的；在线性表的链接存储中，元素之间的逻辑关系是通过____________决定的。

5、一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;

(2)p->data=p->next->data; (3)p->next=__________; (4)free(q);

6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成__________，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个__________都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑__________的发生，因此适应数据量变化较大的情况。

7、从顺序表中删除第i个元素时，首先把第i个元素赋给__________带回，接着从_____________开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。

8、向一个长度为n的顺序表中的第i个元素(0

11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。 12、访问单链表中的结点，必须沿着________依次进行。

13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。 14、在______链表上，删除最后一个结点，其算法的时间复杂度为O(1)。

15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data;

(4)p->data=_________。 (5)s-.data=_________。

16、在一个单链表中删除p所指结点时，应执行以下操作： q=p->next;

p_data=p->next->data; p->next=______; free(q);

17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。

18、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是________；在给定值为x的结点后插入一后新结点的时间复杂度是________。

- 27 -

19、在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链式存储中，元素之间的逻辑关系是通过______决定的。

20、在一个长度为n的顺序表中删除第i个元素(1

24、在顺序表_____元素后面插入一个元素，不需要移动任何元素。 25、插入顺序表的______元素，需要移动的元素最多。

26、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为______。 27、求单链表长度的时间复杂度为_______。

28、删除单链表L中某结点*p之后的一个结点，其时间复杂度为______。 29、删除单链表L中某结点*p之前的一个结点，其时间复杂度为______。

30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时，应执行以下操作： (1)q=p->next;

(2)p->data=q->data; (3)p->next = _____; (4)free(q);

31、在一个单链表中的p所指结点之后插入*s结点时，应执行s->next=_____和p->next______的操作。 32、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。

33、删除双链表L中某结点*p之后的一个结点，其时间复杂度为_______。 34、删除双链表L中某结点*p之前的一个结点，其时间复杂度为_______。 35、在非循环的______链表中，可以用表尾指针代替表头指针。

36、对于双链表，在两个结点之间插入一个新结点需要修改的指针共______。 37、在一个双链表中，若要在*p结点之前插入结点*q，则执行的操作是______。 38、循环单链表L为空的条件是______。

39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过______来实现的. 40、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。

41、对于一个单链接存储的线性表，在表头插入结点的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。

42、在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为____________，后继元素的下标为____________。

43、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为____________，若p为一个数组a中的下标，则其后继结点的下标的____________。

44、在循环单链表中，最后一个结点的指针域指向____________结点。

45、在双向链表中每个结点包含有两个指针域，一个指向其____________结点，另一个指向其____________结点。

46、在循环双向链表中表头结点的左指针域指向____________结点，最后一个结点的右指针域指向____________结点。

47、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。

50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。

- 28 -

相关推荐：